package test.n00600;


import static utils.Tools.listOf;

public class Problem00641 {
    public static void main(String[] args) {
        println(new int[][]{
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1},
        });
    }

    public static void println(int[][] grid) {
        Solution ss = new Solution();
        System.out.println(listOf(grid) + "," + ss.minPathSum(grid));
    }

    public static class Solution {

        /**
         * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
         * <p>
         * 说明：每次只能向下或者向右移动一步。
         * <p>
         * 解题思路:
         * 动态规划
         * <p>
         * 当 i>0i>0 且 j=0j=0 时，\textit{dp}[i][0]=\textit{dp}[i-1][0]+\textit{grid}[i][0]dp[i][0]=dp[i−1][0]+grid[i][0]。
         * 当 i=0i=0 且 j>0j>0 时，\textit{dp}[0][j]=\textit{dp}[0][j-1]+\textit{grid}[0][j]dp[0][j]=dp[0][j−1]+grid[0][j]。
         * 当 i>0i>0 且 j>0j>0 时，\textit{dp}[i][j]=\min(\textit{dp}[i-1][j],\textit{dp}[i][j-1])+\textit{grid}[i][j]dp[i][j]=min(dp[i−1][j],dp[i][j−1])+grid[i][j]。
         *
         * @param grid
         * @return
         */
        public int minPathSum(int[][] grid) {
            int n = grid.length;
            int m = grid[0].length;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i == 0 && j == 0) {
                        continue;
                    }
                    if (i == 0 && j > 0) {
                        grid[i][j] = grid[i][j - 1] + grid[i][j];
                    } else if (i > 0 && j == 0) {
                        grid[i][j] = grid[i - 1][j] + grid[i][j];
                    } else {
                        grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                    }
                }
            }
            return grid[n - 1][m - 1];
        }
    }
}
